package org.example.algorithm.matrix;

import java.util.ArrayList;
import java.util.List;

public class SpiralOrderSolution {
    public static void main(String[] args) {
        int[][] matrix = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
        SpiralOrderSolution solution = new SpiralOrderSolution();
        List<Integer> res = solution.spiralOrder2(matrix);
        System.out.println(res);
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0) {
            return res;
        }
        int endRow = matrix.length - 1;
        int endCol = matrix[0].length - 1;
        int startRow = 0;
        int startCol = 0;
        while (startRow <= endRow && startCol <= endCol) {
            for (int i=startCol;i<=endCol;i++) {
                res.add(matrix[startRow][i]);
            }
            startRow++;
            for (int i=startRow;i<=endRow;i++) {
                res.add(matrix[i][endCol]);
            }
            endCol--;
            //关键判断
            if (startRow <= endRow) {
                for (int i=endCol;i>=startCol;i--) {
                    res.add(matrix[endRow][i]);
                }
            }
            endRow--;
            //关键判断
            if (startCol <= endCol) {
                for (int i=endRow;i>=startRow;i--) {
                    res.add(matrix[i][startCol]);
                }
            }
            startCol++;
        }
        return res;
    }

    public List<Integer> spiralOrder2(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int count = row * col;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] visited = new boolean[row][col];
        int direction = 0;
        int curRow = 0;
        int curCol = 0;
        for (int i=0;i<count;i++) {
            res.add(matrix[curRow][curCol]);
            visited[curRow][curCol] = true;
            int nextRow = curRow + directions[direction][0];
            int nextCol = curCol + directions[direction][1];
            if (nextRow < 0 || nextRow > row-1 || nextCol < 0 || nextCol > col-1 || visited[nextRow][nextCol]) {
                direction = (direction + 1) % 4;
            }
            curRow = curRow + directions[direction][0];
            curCol = curCol + directions[direction][1];
        }
        return res;
    }
}
